{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Subsequences That Satisfy the Given Sum Condition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numSubseq"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #满足条件的子序列数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> 和一个整数 <code>target</code> 。</p>\n",
    "\n",
    "<p>请你统计并返回 <code>nums</code> 中能满足其最小元素与最大元素的 <strong>和</strong> 小于或等于 <code>target</code> 的 <strong>非空</strong> 子序列的数目。</p>\n",
    "\n",
    "<p>由于答案可能很大，请将结果对<meta charset=\"UTF-8\" />&nbsp;<code>10<sup>9</sup>&nbsp;+ 7</code>&nbsp;取余后返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,5,6,7], target = 9\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>有 4 个子序列满足该条件。\n",
    "[3] -&gt; 最小元素 + 最大元素 &lt;= target (3 + 3 &lt;= 9)\n",
    "[3,5] -&gt; (3 + 5 &lt;= 9)\n",
    "[3,5,6] -&gt; (3 + 6 &lt;= 9)\n",
    "[3,6] -&gt; (3 + 6 &lt;= 9)\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,3,6,8], target = 10\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>有 6 个子序列满足该条件。（nums 中可以有重复数字）\n",
    "[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,3,3,4,6,7], target = 12\n",
    "<strong>输出：</strong>61\n",
    "<strong>解释：</strong>共有 63 个非空子序列，其中 2 个不满足条件（[6,7], [7]）\n",
    "有效序列总数为（63 - 2 = 61）\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>\n",
    "\t<li><code>1 &lt;= target &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-subsequences-that-satisfy-the-given-sum-condition](https://leetcode.cn/problems/number-of-subsequences-that-satisfy-the-given-sum-condition/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-subsequences-that-satisfy-the-given-sum-condition](https://leetcode.cn/problems/number-of-subsequences-that-satisfy-the-given-sum-condition/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,5,6,7]\\n9', '[3,3,6,8]\\n10', '[2,3,3,4,6,7]\\n12']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans, j = 0, n-1\n",
    "        for i in range(n):\n",
    "            if nums[i] * 2 > target:\n",
    "                break\n",
    "            while nums[i] + nums[j] > target:\n",
    "                j -= 1\n",
    "            ans += pow(2, j - i,MOD )\n",
    "        return ans % MOD\n",
    "\n",
    "\n",
    "       \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        right, ans, mod=n-1,0, 10**9+7\n",
    "        for left,c in enumerate(nums):\n",
    "            while right>=left and c+nums[right]>target:\n",
    "                right-=1\n",
    "            if right>=left:\n",
    "                # ans+=(1<<(right-left))%mod  # left以外的每个数字选或不选\n",
    "                ans=(ans%mod+pow(2,right-left,mod))%mod\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "\n",
    "        nums.sort()\n",
    "        ans = j = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] * 2 > target:\n",
    "                break\n",
    "            # 指针回撤\n",
    "            # while j == n or nums[i] + nums[j] > target:\n",
    "            #     j -= 1\n",
    "            # while j < n and nums[i] + nums[j] <= target:\n",
    "            #     j += 1\n",
    "            j = bisect.bisect_right(nums, target - nums[i])\n",
    "            ans += pow(2, j - i - 1, MOD)\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans, j = 0, n-1\n",
    "        for i in range(n):\n",
    "            if nums[i] * 2 > target:\n",
    "                break\n",
    "            while nums[i] + nums[j] > target:\n",
    "                j -= 1\n",
    "            ans += pow(2, j - i, MOD)\n",
    "        return ans % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        i, j = 0, len(nums) - 1\n",
    "        ans = 0\n",
    "        while i <= j:\n",
    "            if nums[i] + nums[j] <= target:\n",
    "                ans += 1 << (j - i)\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "        return ans % (10**9 + 7)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fast_pow(self, n, a):\n",
    "        if a==0: return 1\n",
    "        if a==1: return n\n",
    "        if a%2: return self.fast_pow(n, a//2)**2*n% 1000000007\n",
    "        return self.fast_pow(n, a//2)**2% 1000000007\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            p = bisect.bisect_right(nums, target-nums[i])\n",
    "            if p>i: res += self.fast_pow(2, p-i-1) % 1000000007\n",
    "        return res%1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans, j = 0,0\n",
    "        for i in range(n):\n",
    "            if nums[i] * 2 > target:\n",
    "                break\n",
    "            while j == n or nums[i] + nums[j] > target:\n",
    "                j -= 1\n",
    "            while j < n and nums[i] + nums[j] <= target:\n",
    "                j += 1\n",
    "            ans += pow(2, j - i - 1,MOD )\n",
    "        return ans % MOD\n",
    "\n",
    "\n",
    "       \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        r = n - 1\n",
    "        for l, x in enumerate(nums):\n",
    "            if x * 2 > target:\n",
    "                break\n",
    "            while r > l and x + nums[r] > target:\n",
    "                r -= 1\n",
    "            ans += pow(2, r - l, MOD)\n",
    "        return ans % MOD\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        mod = 10**9 + 7\n",
    "        for i, x in enumerate(nums):\n",
    "            if x + x > target:\n",
    "                break\n",
    "            l = i\n",
    "            r = n - 1\n",
    "            while l < r:\n",
    "                mid = l + r + 1 >> 1\n",
    "                if nums[mid] <= target - x:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            if nums[r] <= target - x:\n",
    "                res = (res + pow(2, r - i, mod)) % mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = j = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] * 2 > target:\n",
    "                break\n",
    "            # 指针回撤\n",
    "            while j == n or nums[i] + nums[j] > target:\n",
    "                j -= 1\n",
    "            while j < n and nums[i] + nums[j] <= target:\n",
    "                j += 1\n",
    "            ans += pow(2, j - i - 1, MOD)\n",
    "        return ans % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        MOD = 1000000007\n",
    "\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for i in range(len(nums)-1, -1, -1):\n",
    "            if nums[i] >= target:\n",
    "                continue\n",
    "            k = bisect.bisect_right(nums, target-nums[i], 0, i+1)\n",
    "            if k > i:\n",
    "                ans += 1\n",
    "                k -= 1\n",
    "            if k == 0:\n",
    "                continue\n",
    "            ans += pow(2, i, MOD) - pow(2, i-k, MOD)\n",
    "        \n",
    "        return ans % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        mod = 1000000007\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        # 枚举第一个元素\n",
    "        p = [0] * n\n",
    "        p[0] = 1\n",
    "        for i in range(1, n):\n",
    "            p[i] = (p[i - 1] << 1) % mod\n",
    "        for i in range(n):\n",
    "            x = nums[i]\n",
    "            if x > target // 2:\n",
    "                break\n",
    "            # 枚举到的数字本身也算作和自己匹配的一种\n",
    "            l, r = i, n - 1\n",
    "            while l < r:\n",
    "                mid = l + ((r - l) >> 1) + 1\n",
    "                if nums[mid] > target - x:\n",
    "                    r = mid - 1\n",
    "                else:\n",
    "                    l = mid\n",
    "            if nums[l] <= target - x:\n",
    "                ans = (ans + p[l - i]) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        nums.sort()\n",
    "        l, r = 0, len(nums) - 1\n",
    "        res = 0\n",
    "        while l <= r:\n",
    "            if nums[l] + nums[r] > target:\n",
    "                r -= 1\n",
    "            else:\n",
    "                res = (res + pow(2, r - l, mod)) % mod\n",
    "                l += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#from scipy.special import comb\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()        \n",
    "        m=len(nums)\n",
    "        index=bisect.bisect_left(nums,target//2+1)\n",
    "        c=0\n",
    "\n",
    "        for i in range(index):\n",
    "            #if nums[i]*2>target:\n",
    "            #    break\n",
    "            j=bisect.bisect_right(nums,target-nums[i])\n",
    "            #if j!=0:\n",
    "            c=c+pow(2,j-i-1,10**9+7)\n",
    "            #print(i,j)\n",
    "\n",
    "        return int(c%(10**9+7))\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "        res, mod = 0, (10**9 + 7)\n",
    "\n",
    "        left, right = 0, len(nums) - 1\n",
    "        while  left <= right:\n",
    "            if (nums[left] + nums[right]) > target:\n",
    "                right -= 1\n",
    "            else:\n",
    "                res += 1 << (right - left)\n",
    "                left += 1\n",
    "        return res % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        mod = int(1e9 + 7)\n",
    "        res = 0\n",
    "        nums.sort()\n",
    "\n",
    "        f = [1] + [0] * len(nums)\n",
    "\n",
    "        for i in range(1, len(f)):\n",
    "            f[i] = f[i - 1] * 2 % mod\n",
    "\n",
    "        j = len(nums) - 1\n",
    "        for i, n in enumerate(nums):\n",
    "            if 2 * n > target:\n",
    "                break\n",
    "\n",
    "            while i <= j and nums[i] + nums[j] > target:\n",
    "                j -= 1\n",
    "            res = (res + f[j - i]) % mod\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: list[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        left = 0\n",
    "        right = len(nums)-1\n",
    "        mod = 1000000007\n",
    "        tmp = len(nums) * [0]\n",
    "        tmp[0] = 1\n",
    "        i = 1\n",
    "        cnt = 0\n",
    "        while(i<len(tmp)):\n",
    "            tmp[i] = (tmp[i-1] * 2) % mod\n",
    "            i+=1\n",
    "        while left<=right:\n",
    "            if nums[left]+nums[right]>target:\n",
    "                right-=1\n",
    "            else:\n",
    "                cnt = (cnt + tmp[right-left])%mod\n",
    "                left += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        P = 1e9+7\n",
    "        n = len(nums)\n",
    "        # 记录2的i次方\n",
    "        f = [1]+[0]*(n-1)\n",
    "        for i in range(1,n):\n",
    "            f[i] = f[i-1]*2%P # 在后面用于相乘，所以可以提前取模\n",
    "\n",
    "        nums.sort()\n",
    "        cnt = 0\n",
    "        for i,num in enumerate(nums):\n",
    "            if nums[i] * 2 > target:\n",
    "                break\n",
    "            idx = bisect_right(nums,target-nums[i])-1 #大于阈值的第一个-1\n",
    "            if idx >= i:\n",
    "                cnt+=f[idx-i]\n",
    "        return int(cnt%P)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        if nums[0] * 2 > target:\n",
    "            return 0\n",
    "            \n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "        res = 0\n",
    "        while left <= right:\n",
    "            if nums[left] + nums[right] <= target:\n",
    "                res += 1 << (right-left)\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        return res%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        i, j = 0, len(nums) - 1\n",
    "        ans = 0\n",
    "        while i <= j:\n",
    "            if nums[i] + nums[j] <= target:\n",
    "                ans += 2**(j - i)\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "        return ans % (10**9 + 7)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        if nums[0] * 2 > target:\n",
    "            return 0\n",
    "        res = 0\n",
    "        l = 0\n",
    "        r = len(nums)-1\n",
    "        while l <= r:\n",
    "            if nums[l] + nums[r] <= target:\n",
    "                res += 2**(r-l)\n",
    "                l += 1\n",
    "            else:\n",
    "                r -= 1\n",
    "        return res%(10**9+7)\n",
    "        \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        left, right = 0, n-1\n",
    "        if nums[0]*2 > target:return ans\n",
    "        while left <= right:\n",
    "            if nums[left]+nums[right] <= target:\n",
    "                ans += 1<<(right-left)\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        return ans%(10**9+7)\n",
    "        '''\n",
    "        ans = 0\n",
    "        pre = n-1\n",
    "        for i in range(n):\n",
    "            if nums[i]*2 > target:break\n",
    "            if i > 0 and nums[i-1] == nums[i]:\n",
    "                ans += 2**(right-i)\n",
    "                continue\n",
    "            temp = target - nums[i]\n",
    "            left, right = i, pre\n",
    "            while left <= right:\n",
    "                mid = left + (right-left)//2\n",
    "                if nums[mid] > temp:\n",
    "                    right = mid-1\n",
    "                else:\n",
    "                    left = mid+1\n",
    "            pre = right\n",
    "            ans += 2**(right-i)\n",
    "\n",
    "        return ans%(10**9+7)\n",
    "        '''\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        if nums[0] * 2 > target:\n",
    "            return 0\n",
    "            \n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "        res = 0\n",
    "        while left <= right:\n",
    "            if nums[left] + nums[right] <= target:\n",
    "                res += 2**(right-left)\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        return res%(10**9+7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        if nums[0]*2>target:\n",
    "            return 0\n",
    "        count=0    # 记录满足的子序列的个数\n",
    "        i,j=0,len(nums)-1\n",
    "        while i<=j:\n",
    "            if nums[i]+nums[j]<=target:  # 取得子序列的最小值和最大值，与target进行比较\n",
    "                count+=2**(j-i)\n",
    "                i+=1\n",
    "            else:\n",
    "                j-=1\n",
    "        return count%(10**9+7) # 最终返回满足的子序列的总数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]*2 > target:\n",
    "                break\n",
    "            j = bisect.bisect_left(nums, target-nums[i]+1)-1\n",
    "            # print(nums[i], j)\n",
    "            if j >= i:\n",
    "                ans += 1 << (j-i)\n",
    "        \n",
    "        return ans % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        if nums[0] > target:return 0\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        left = 0\n",
    "        right = n - 1\n",
    "        while left <= right:\n",
    "            if nums[left] + nums[right] <= target:\n",
    "                ans += 2 **(right - left) #[left,right]区间内的全排序组合个数\n",
    "                left += 1\n",
    "            else:right -= 1\n",
    "        return ans % (10**9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]*2 > target:\n",
    "                break\n",
    "            j = bisect.bisect_right(nums, target-nums[i])-1\n",
    "            # print(nums[i], j)\n",
    "            if j >= i:\n",
    "                ans += 1 << (j-i)\n",
    "        \n",
    "        return ans % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        left, right = 0, len(nums) - 1\n",
    "        # 寻找右边界开始满足的端点\n",
    "        res = 0\n",
    "        while left <= right:\n",
    "            # 该区间的满足最大最小\n",
    "            if nums[left] + nums[right] <= target:\n",
    "                res += 2**(right - left)\n",
    "                res %= 10**9 + 7\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        return int(res % (10**9 + 7))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        res = 0\n",
    "        nums.sort()\n",
    "        if nums[0] * 2 > target:\n",
    "            return 0\n",
    "        left, right = 0, len(nums) - 1\n",
    "        while left <= right:\n",
    "            if nums[left] + nums[right] <= target:\n",
    "                res += 2 ** (right-left) \n",
    "                left += 1\n",
    "            elif nums[left] + nums[right] > target:\n",
    "                right -= 1\n",
    "        return res % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        mod = 10 ** 9 + 7\n",
    "        r = len(nums) - 1\n",
    "        for i, left in enumerate(nums):\n",
    "            while (left + nums[r] > target) and i <= r:\n",
    "                r -= 1\n",
    "            if i <= r:\n",
    "                res += (2 ** (r - i)) \n",
    "        return res % mod\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        right, ans, mod=n-1,0, 10**9+7\n",
    "        for left,c in enumerate(nums):\n",
    "            while right>=left and c+nums[right]>target:\n",
    "                right-=1\n",
    "            if right>=left:\n",
    "                # ans+=(1<<(right-left))%mod  # left以外的每个数字选或不选\n",
    "                ans=(ans%mod+pow(2,right-left,mod))%mod\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        result = 0\n",
    "        right = n - 1\n",
    "        for i in range(n):\n",
    "            if(i > right):\n",
    "                break\n",
    "            left = i + 1\n",
    "            while(left <= right):\n",
    "                mid = (left+right)>>1\n",
    "                if(nums[i] + nums[mid] <= target):\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            result += (1<<(right-i))-1\n",
    "            if(nums[i]*2<= target):\n",
    "                result += 1\n",
    "        return result % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        mod = 10**9+7\n",
    "        r = len(nums)-1\n",
    "        l = 0\n",
    "        ans = 0\n",
    "        while r>=0:\n",
    "            while l<=r and nums[l]+nums[r]<=target:\n",
    "                l += 1\n",
    "            # print(ans, l, r, (1<<r), (1<<(max(r-l, 0))))\n",
    "            if l>r:\n",
    "                ans = (ans + (1<<r)) % mod\n",
    "            else:\n",
    "                ans = (ans + (1<<r) - (1<<(max(r-l, 0)))) % mod\n",
    "            r -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        result = 0\n",
    "        right = n - 1\n",
    "        for i in range(n):\n",
    "            if(i > right):\n",
    "                break\n",
    "            left = i + 1\n",
    "            while(left <= right):\n",
    "                mid = (left+right)>>1\n",
    "                if(nums[i] + nums[mid] <= target):\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            result += 2**(right-i)-1\n",
    "            if(nums[i]*2<= target):\n",
    "                result += 1\n",
    "        return result % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "\n",
    "        nums.sort()\n",
    "        l = 0\n",
    "        r = len(nums) - 1\n",
    "        count = 0\n",
    "        if nums[0] * 2 > target:\n",
    "            return 0\n",
    "        while l <= r:\n",
    "            if nums[l] + nums[r] > target:\n",
    "                r -= 1\n",
    "            else:\n",
    "                count += 2**(r-l)\n",
    "                l += 1\n",
    "        return count % (10**9+7)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        if nums[0] * 2 > target:\n",
    "            return 0\n",
    "\n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "        ans = 0\n",
    "        while left<=right:\n",
    "            if nums[left] + nums[right] <= target:\n",
    "                ans += 2**(right-left)\n",
    "                left += 1\n",
    "            else:\n",
    "                right -=1 \n",
    "        return ans % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        \"\"\" nums.sort()\n",
    "        n = len(nums)\n",
    "        i = 0 \n",
    "        j = 0\n",
    "        res = 0\n",
    "        MOD = 10**9+7\n",
    "        \n",
    "        while i < n and nums[i] <= target/2:\n",
    "            j = bisect_right(nums,target-nums[i]) - 1\n",
    "            res += 2**(j-i)\n",
    "            i += 1\n",
    "        return res%MOD \"\"\"\n",
    "        MOD = 10**9+7\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] * 2 > target:\n",
    "                break\n",
    "            j = bisect.bisect_right(nums, target - nums[i])\n",
    "            ans += pow(2, j - i - 1, MOD)\n",
    "        return ans % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        right, ans, mod=n-1,0, 10**9+7\n",
    "        for left,c in enumerate(nums):\n",
    "            while right>=left and c+nums[right]>target:\n",
    "                right-=1\n",
    "            if right>=left:\n",
    "                # ans+=(1<<(right-left))%mod  # left以外的每个数字选或不选\n",
    "                ans=(ans%mod+pow(2,right-left,mod))%mod\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        i = 0 \n",
    "        j = 0\n",
    "        res = 0\n",
    "        MOD = 10**9+7\n",
    "        \n",
    "        while i < n and nums[i] <= target/2:\n",
    "            j = bisect_left(nums,target-nums[i]+1) - 1\n",
    "            #res += 2**(j-i)\n",
    "            res += pow(2, j - i, MOD)\n",
    "            i += 1\n",
    "        return res%MOD\n",
    "\n",
    "\n",
    "        \"\"\" MOD = 10**9+7 #儿酒醉-排序+二分\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] * 2 > target:\n",
    "                break\n",
    "            j = bisect.bisect_right(nums, target - nums[i])\n",
    "            ans += pow(2, j - i - 1, MOD)\n",
    "        return ans % MOD \"\"\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        right, ans, mod=n-1,0, 10**9+7\n",
    "        for left,c in enumerate(nums):\n",
    "            while right>=left and c+nums[right]>target:\n",
    "                right-=1\n",
    "            if right>=left:\n",
    "                ans=(ans%mod+pow(2,right-left,mod))%mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, a: List[int], t: int) -> int:\n",
    "        ans = 0\n",
    "        m = 10**9 + 7 \n",
    "        a.sort()\n",
    "        n = len(a)\n",
    "        j = n - 1\n",
    "        for i in range(n):\n",
    "            if i>j:\n",
    "                return ans%m \n",
    "            while a[i] + a[j] > t:\n",
    "                j -= 1\n",
    "                if j<i:\n",
    "                    return ans%m  \n",
    "            ans += pow(2, j-i, m)\n",
    "        return ans%m\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    import bisect\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        print(nums,n)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            if nums[i]*2>target:\n",
    "                break\n",
    "            idx=bisect.bisect_right(nums,target-nums[i])\n",
    "            # print(i,idx)\n",
    "            if idx>i:\n",
    "                ans+=2**(idx-1-i)\n",
    "        return int(ans%(10**9+7))\n",
    "        \n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n= len(nums)\n",
    "        l, r = 0, n-1\n",
    "        ans=0\n",
    "        while l<=r:\n",
    "            if nums[l]+nums[r]<=target:\n",
    "                ans+=1<<(r-l)\n",
    "                l+=1\n",
    "            else:\n",
    "                r-=1\n",
    "        return ans%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        left = 0\n",
    "        right = n - 1\n",
    "        ans = 0\n",
    "        cnt = [0] * (n + 1)\n",
    "        cnt[1] = 1\n",
    "        nums = sorted(nums)\n",
    "        for i in range(2,n+1):\n",
    "            cnt[i] = (cnt[i-1]*2+1)%1000000007\n",
    "        while left <= right:\n",
    "            if nums[left] + nums[right] <= target:\n",
    "                ans = ans + cnt[right-left+1]-cnt[right-left]\n",
    "                ans = ans % 1000000007\n",
    "                left = left + 1\n",
    "            else:\n",
    "                right = right - 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        #解题思路：\n",
    "        #注意要求是子序列，因此先进行排序，其次进行二分\n",
    "\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        right, ans, mod=n-1,0, 10**9+7\n",
    "        for left,c in enumerate(nums):\n",
    "            while right>=left and c+nums[right]>target:\n",
    "                right-=1\n",
    "            if right>=left:\n",
    "                # ans+=(1<<(right-left))%mod  # left以外的每个数字选或不选\n",
    "                ans=(ans%mod+pow(2,right-left,mod))%mod\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            lo = i\n",
    "            hi = n \n",
    "            k = i - 1\n",
    "            while lo < hi:\n",
    "                mi = (lo + hi)//2 \n",
    "                if nums[i] + nums[mi] <= target:\n",
    "                    lo = mi + 1 \n",
    "                else:\n",
    "                    hi = mi\n",
    "            if lo - i > 0:\n",
    "                ans += pow(2, lo - i-1,10**9 + 7)\n",
    "        return ans %(10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        \n",
    "        def search(nums, value):\n",
    "            lo, hi = 0, len(nums)\n",
    "            while lo < hi:\n",
    "                mid = lo + (hi - lo) // 2\n",
    "                if nums[mid] <= value:\n",
    "                    lo = mid + 1\n",
    "                else:\n",
    "                    hi = mid\n",
    "            return lo\n",
    "        \n",
    "        def power(x, n):\n",
    "            MOD = 10 ** 9 + 7\n",
    "            t = x\n",
    "            ans = 1\n",
    "            while n:\n",
    "                if n % 2:\n",
    "                    ans = ans * t % MOD\n",
    "                t = (t * t) % MOD\n",
    "                n //= 2\n",
    "            return ans \n",
    "\n",
    "\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            x = nums[i]\n",
    "            if x * 2 > target:\n",
    "                break\n",
    "            index = search(nums, target - x)\n",
    "            ans += power(2, index - i - 1)\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        f = [0] * 100005\n",
    "        f[0] = 1\n",
    "        for i in range(1, n):\n",
    "            f[i] = f[i - 1] * 2 % MOD\n",
    "        nums = sorted(nums)\n",
    "        ans = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if 2 * num > target:\n",
    "                break\n",
    "            idx = bisect_right(nums, target - num) - 1\n",
    "            ans = (ans + f[idx - i ]) % MOD\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums = sorted(nums)\n",
    "        result = 0\n",
    "        mod = (10**9 + 7)\n",
    "        r = len(nums) - 1\n",
    "        for i, left in enumerate (nums):\n",
    "            while left + nums[r] > target and i <= r:\n",
    "                r -= 1\n",
    "            if i <= r:\n",
    "                result += 2**(r-i)\n",
    "                result %= mod\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        P = 10**9 + 7\n",
    "        f = [1] + [0] * (n - 1)\n",
    "        for i in range(1, n):\n",
    "            f[i] = f[i - 1] * 2 % P\n",
    "\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if nums[i] * 2 > target:\n",
    "                break\n",
    "            maxValue = target - nums[i]\n",
    "            pos = bisect.bisect_right(nums, maxValue) - 1\n",
    "            contribute = f[pos - i] if pos >= i else 0\n",
    "            ans += contribute\n",
    "        \n",
    "        return ans % P\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        mod = int(1e9 + 7)\n",
    "        res = 0\n",
    "        nums.sort()\n",
    "\n",
    "        f = [1] + [0] * len(nums)\n",
    "\n",
    "        for i in range(1, len(f)):\n",
    "            f[i] = f[i - 1] * 2 % mod\n",
    "\n",
    "        j = len(nums) - 1\n",
    "        for i, n in enumerate(nums):\n",
    "            if 2 * n > target:\n",
    "                break\n",
    "\n",
    "            while i <= j and nums[i] + nums[j] > target:\n",
    "                j -= 1\n",
    "            res += f[j - i]\n",
    "            res %= mod\n",
    "        \n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        P = 10**9 + 7\n",
    "        f = [1] + [0] * (n - 1)\n",
    "        for i in range(1, n):\n",
    "            f[i] = f[i - 1] * 2 % P\n",
    "\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if nums[i] * 2 > target:\n",
    "                break\n",
    "            maxValue = target - nums[i]\n",
    "            pos = bisect.bisect_right(nums, maxValue) - 1\n",
    "            contribute = f[pos - i] if pos >= i else 0\n",
    "            ans += contribute\n",
    "        \n",
    "        return ans % P"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        l = 0\n",
    "        f = [1] + [0] * (len(nums) - 1)\n",
    "        for i in range(1, len(nums)):\n",
    "            f[i] = f[i - 1] * 2 % MOD\n",
    "        for r in range(len(nums) - 1, -1, -1):\n",
    "            while l <= r and nums[l] + nums[r] <= target:\n",
    "                l += 1\n",
    "            ans = (ans + f[r] - (f[r - l] if l <= r else 0)) % MOD\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        mod = int(10**9+7)\n",
    "        ret = 0\n",
    "        l, r = 0, len(nums)-1\n",
    "        while l<=r:\n",
    "            if nums[l]+nums[r]>target:\n",
    "                r -= 1\n",
    "            else:\n",
    "                ret = (ret + (1<<(r-l)))%mod\n",
    "                l+=1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        result = 0\n",
    "        right = n - 1\n",
    "        for i in range(n):\n",
    "            if(i > right):\n",
    "                break\n",
    "            left = i + 1\n",
    "            while(left <= right):\n",
    "                mid = (left+right)>>1\n",
    "                if(nums[i] + nums[mid] <= target):\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            result += (1<<(right-i))-1\n",
    "            if(nums[i]*2<= target):\n",
    "                result += 1\n",
    "        return result % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        '''\n",
    "        ans = 0\n",
    "        left, right = 0, n-1\n",
    "        if nums[0]*2 > target:return ans\n",
    "        while left <= right:\n",
    "            if nums[left]+nums[right] <= target:\n",
    "                ans += 1<<(right-left)\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        return ans%(10**9+7)\n",
    "        '''\n",
    "        ans = 0\n",
    "        pre = n-1\n",
    "        for i in range(n):\n",
    "            if nums[i]*2 > target:break\n",
    "            if i > 0 and nums[i-1] == nums[i]:\n",
    "                ans += 2**(right-i)\n",
    "                continue\n",
    "            temp = target - nums[i]\n",
    "            left, right = i, pre\n",
    "            while left <= right:\n",
    "                mid = left + (right-left)//2\n",
    "                if nums[mid] > temp:\n",
    "                    right = mid-1\n",
    "                else:\n",
    "                    left = mid+1\n",
    "            pre = right\n",
    "            ans += 1<<(right-i)\n",
    "\n",
    "        return ans%(10**9+7)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        M = 10**9+7\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        result = 0\n",
    "        right = n - 1\n",
    "        for i in range(n):\n",
    "            if(i > right):\n",
    "                break\n",
    "            left = i + 1\n",
    "            while(left <= right):\n",
    "                mid = (left+right)>>1\n",
    "                if(nums[i] + nums[mid] <= target):\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            result += (1<<(right-i))-1\n",
    "            if(nums[i]*2<= target):\n",
    "                result += 1\n",
    "        return result % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        M = 10**9+7\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        result = 0\n",
    "        right = n - 1\n",
    "        for i in range(n):\n",
    "            if(i > right):\n",
    "                break\n",
    "            left = i + 1\n",
    "            while(left <= right):\n",
    "                mid = (left+right)>>1\n",
    "                if(nums[i] + nums[mid] <= target):\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            result += (1<<(right-i))-1\n",
    "            if(nums[i]*2<= target):\n",
    "                result += 1\n",
    "        return result % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        result = 0\n",
    "        right = n - 1\n",
    "        for i in range(n):\n",
    "            if(i > right):\n",
    "                break\n",
    "            left = i + 1\n",
    "            while(left <= right):\n",
    "                mid = (left+right)>>1\n",
    "                if(nums[i] + nums[mid] <= target):\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            result += 2**(right-i)-1\n",
    "            if(nums[i]*2<= target):\n",
    "                result += 1\n",
    "        return result % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        if nums[0]*2>target:\n",
    "            return 0\n",
    "        count=0    # 记录满足的子序列的个数\n",
    "        i,j=0,len(nums)-1\n",
    "        while i<=j:\n",
    "            if nums[i]+nums[j]<=target:  # 取得子序列的最小值和最大值，与target进行比较\n",
    "                # count+=2**(j-i)\n",
    "                count += 1<<(j-i)   # 利用位运算，提高效率\n",
    "                i+=1\n",
    "            else:\n",
    "                j-=1\n",
    "        return count%(10**9+7) # 最终返回满足的子序列的总数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if nums[i]*2 > target:break\n",
    "            temp = target - nums[i]\n",
    "            left, right = 0, n-1\n",
    "            while left <= right:\n",
    "                mid = left + (right-left)//2\n",
    "                if nums[mid] > temp:\n",
    "                    right = mid-1\n",
    "                else:\n",
    "                    left = mid+1\n",
    "\n",
    "            ans += 2**(right-i)\n",
    "\n",
    "        return ans%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        # print(nums)\n",
    "        result=0\n",
    "        for start in range(len(nums)):\n",
    "            if nums[start]>target:\n",
    "                break\n",
    "            elif nums[start]*2<=target:\n",
    "                count=1\n",
    "            else:\n",
    "                count=0\n",
    "\n",
    "            left = start\n",
    "            right = len(nums)-1\n",
    "            while left <= right:\n",
    "                mid = (left + right) // 2\n",
    "                if nums[mid] + nums[start] > target:\n",
    "                    right = mid - 1\n",
    "                elif nums[mid] + nums[start] < target:\n",
    "                    if mid+1<len(nums) and nums[mid+1] + nums[start]>target:\n",
    "                        break\n",
    "                    left = mid + 1\n",
    "                elif mid+1<len(nums) and nums[mid] + nums[start] == target and nums[mid+1] + nums[start] == target:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    break\n",
    "            count+=mid-start\n",
    "            # print(count)\n",
    "            if count>0:\n",
    "                result+=2**(count-1)\n",
    "        result=result%(10**9 + 7)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        if nums[0]*2>target:\n",
    "          return 0\n",
    "        l=0\n",
    "        r=len(nums)-1\n",
    "        res=0\n",
    "        while l<=r:\n",
    "            if nums[l]+nums[r]<=target:\n",
    "                res+=2**(r-l);\n",
    "                l+=1\n",
    "            else:\n",
    "                r-=1\n",
    "        return res%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        mod = 10**9 +7\n",
    "        res = 0 \n",
    "        for left in range(n):\n",
    "            right = bisect.bisect_right(nums, target - nums[left])-1\n",
    "            if right >= left:\n",
    "                res += pow(2, right - left)\n",
    "        return res % (mod)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    import bisect\n",
    "    def numSubseq(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        print(nums,n)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            idx=bisect.bisect_right(nums,target-nums[i])\n",
    "            # print(i,idx)\n",
    "            if idx>i:\n",
    "                ans+=2**(idx-1-i)\n",
    "        return int(ans%(10**9+7))\n",
    "        \n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "                    \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
